package com.khiker.binary;

public class P338_CountBits {

	public int[] countBits(int n) {
		int[] res = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			res[i] = res[i >> 1] + (i & 1);
		}
		return res;
	}


	public int[] countBits2(int n) {
		int[] res = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			res[i] = (i & 1) == 1 ? res[i - 1] + 1 : res[i >> 1];
		}
		return res;
	}

	public int[] countBits1(int n) {
		int[] res = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			res[i] = count(i);
		}
		return res;
	}

	private int count(int n) {
		int result = 0;
		while (n > 0) {
			result += n & 1;
			n >>= 1;
		}
		return result;
	}
}
